1899B - 250 Thousand Tons of TNT - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb  push_back
#define mp  make_pair
#define IO_FAST                 ios_base::sync_with_stdio(false); cin.tie(NULL);
#define testcase                int t; cin >> t; while(t--)
#define inputvec(v1, n)         for(int i=0; i<n; i++) {int x; cin >> x; v1.pb(x);}
#define inputvecp(v1, n)        for(int i=0; i<n; i++) {int x, y; cin >> x >> y; v1.pb(mp(x,y));}
#define sort(v1)                sort(v1.begin(), v1.end())
#define reverse(v1)             reverse(v1.begin(), v1.end())
#define deb(x)                  cout << #x << ' ' <<  '=' << ' ' << x << endl;
#define print(x)                cout << #x << endl;
#define tolower(s1)             transform(s1.begin(), s1.end(), s1.begin(), ::tolower)
#define toupper(s1)             transform(s1.begin(), s1.end(), s1.begin(), ::toupper)
#define remove_char(s1, a)      s1.erase(remove(s1.begin(), s1.end(), 'a'), s1.end())  // does not work!
#define upperbound(v1, k)       upper_bound(v1.begin(), v1.end(), k)
#define lowerbound(v1, k)       lower_bound(v1.begin(), v1.end(), k)
#define auto1(v1)               for(auto &num1:v1) {cout << num1 << ' ';} cout << endl;
#define auto2(vp1)              for(auto &num1:vp1) {cout << num1.first << ' ' <<num1.second << endl;}
#define auto3(vv1)				for(auto &num1:vv1) {for(auto &num2:num1){cout << num2 <<" ";}cout<<endl;}
int gcd(int a,int b)            { if (b==0) return a; return gcd(b, a%b); } // take a=0;
int lcm(int a,int b)            { return a/gcd(a,b)*b; }  // take a = v[0];
const int N = 1e5+10;
vector<int> dp(N, -1);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//======================================================================================================//
vector<int> primefactors; // Does the primefactorisation of a number;
void factorize(int n)
{
    while(n%2==0)   primefactors.pb(2),   n = n/2;
    for(int i=3; i<=sqrt(n); i=i+2)   while(n%i==0)   primefactors.pb(i),  n = n/i;
    if(n>2) primefactors.pb(n);
}
//======================================================================================================//
vector<int> divisors; // Gives me all the different factors.
void factors(int n)
{
    for(int i=1; i<=n; i++){ if(n%i==0)  divisors.pb(i);}
}
//======================================================================================================//
bool isSubsequence(string s1, string s2) // to check if string s1 is a subsequence of string s2;
{
    int i=0, j=0;
    while(i<s1.size() && j<s2.size()){
    if(s1[i] == s2[j]) {i++;} j++;}
    return (i == s2.size());
}
//======================================================================================================//
vector<vector<int>> subsets;  // To Generate all the subsets of a vector;
void generatesubset(vector<int> &subset, int i, vector<int> v1)
{
    if(i==v1.size()) {subsets.pb(subset); return;}
    generatesubset(subset, i+1, v1);  // Inputvec(v1, n);
    subset.pb(v1[i]);  generatesubset(subset, i+1, v1);   subset.pop_back();
}
//  generatesubset(subset, 0, v1); auto3(subsets);

//======================================================================================================//
void generatesubseq(string s1, string ans) // To generate all the subsequence of a string
{
    if(s1.size()==0){cout << ans << endl;  return;}  char c1 = s1[0];   string rest = s1.substr(1);
    generatesubseq(rest, ans);  generatesubseq(rest, ans+c1);
}   // generatesubseq(s1, ''); -->  Inside Signed main()

//======================================================================================================//
string binary(int num)  // convert a decimal number to binary number
{
    string s1="";
    for(int i=64; i>=0; i--)
    {
        if((num>>i & 1)==1)    s1+='1';  
        else    s1+='0';
    }
    return s1;
}
//======================================================================================================//
int decimal(const string &binaryString) 
{
    int number=0, base=1;
    for (int i = binaryString.length()-1; i>=0; i--) 
    {
        if(binaryString[i] == '1'){
            number += base;
        }
        base *= 2;
    }
    return number;
}
//======================================================================================================//
bool find(string s1, string s2)
{
    size_t found = s1.find(s2);
    if(found != string::npos)
    {
        return true;
    }
    return false;
}
//======================================================================================================//
signed main()
{
    IO_FAST
    testcase
    {
        int n;
        cin >> n;
        vector<int> v1;
        inputvec(v1, n);
        if(n==1)
        {
            cout << 0 << endl;
        }
        else
        {
            vector<int> divisors;
            for(int i=1; i<=sqrt(n); i++)
            {
                if(n%i==0)
                {
                    int a = i;
                    int b = n/i;

                    divisors.pb(a);
                    if(a!=b)
                    {
                        divisors.pb(b);
                    }
                }
            }
            sort(divisors);
            divisors.pop_back();

            int ans = 0;
            vector<int> v;
            for(int i=0; i<divisors.size(); i++)
            {
                int num = divisors[i];
                vector<int> v2;
                int sum=0;
                int count=0;
                for(int j=0; j<n; j++)
                {
                    sum += v1[j];
                    count++;
                    if(count==num)
                    {
                        v2.pb(sum);
                        sum=0;
                        count=0;
                    }
                }
                sort(v2);
                int diff = v2[v2.size()-1]-v2[0];
                v.pb(diff);
            }

            sort(v);
            cout << v[v.size()-1] << endl;
        }
        
    }
}